var Side = { 'RED': 0, 'BLUE': 1 }

function Piece(side, value)
{
	this.side = side;
	this.value = value;
}

var Action = { 'ATTACK': 0, 'DESTROY': 1, 'MOVE': 2, 'PASS': 3 }

function Turn(action, from, to)
{
    this.action = action;
    this.from = from;
    this.to = to;
}

function initialstate(width, height, pieces)
{
    var cells = [];
    var x, y;
   
	for(var x = 0; x < width; ++x)
    {	
	    for(var y = 0; y < height; ++y)
	    {
            var rank_red = pieces-x-y;
            var rank_blue = pieces-(width-1-x)-(height-1-y);

		    cells[y * width + x] =
			    (rank_red > 0) ? (new Piece(Side.RED, rank_red)) :
				    (rank_blue > 0) ? (new Piece(Side.BLUE, rank_blue)) : null;
	    }
    }
    
    return cells;
}

function HierarkiaInfo(width, height, pieces)
{
    this.width = width;
    this.height = height;
    this.pieces = pieces;
}

function Hierarkia(info, cells, lastMove)
{
	this.cells =
	    (cells) ?
	    cells :
	    initialstate(info.width, info.height, info.pieces);
	this.lastMove = lastMove;

	var width = info.width;
	var height = info.height;
	var pieces = info.pieces;
	
	this.homezone = function(x, y)
	{ 
        var rank_red = pieces-x-y;
        var rank_blue = pieces-(width-1-x)-(height-1-y);
		return (rank_red > 0) ? (Side.RED) :
					(rank_blue > 0) ? (Side.BLUE) : undefined;
 	}
 
	this.get = function(x, y) { return this.cells[y * width + x]; }
	this.owner = function(x, y) { return this.homezone(x, y); }
	this.sidePieces = function(side) { return this.cells.filter(function (p) { return (p) ? p.side == side : false }); }

	this.firepower = function(x, y)
	{
		var hierarkia = this;
		function fp(x, y, side)
		{
			var piece = hierarkia.get(x, y);
			if(piece != null){
				if(piece.side == side){
					return piece.value;
				} else {
					return piece.value * -1;
				}
			}
			return 0;
		}

		var piece = this.get(x, y);
        if(!piece) return 0;
		if(piece.side == this.homezone(x, y)) return 0;

		var p = 0;
		if(x > 0) { p += fp(x-1, y, piece.side); }
		if(x < width) { p += fp(x+1, y, piece.side); }
		if(y > 0) { p += fp(x, y-1, piece.side); }
		if(y < height) { p+= fp(x, y+1, piece.side); }
		return p;
	}
	
	this.empty = function(x, y) {
	    if(this.get(x,y)) return false;
	    return true;
	}

	this.isAttacking = function()
	{
		if(this.lastMove && this.lastMove.length > 2) throw "invalid last moves" + JSON.stringify(this.lastMove);
		if(this.lastMove && this.lastMove.length == 2 &&
			this.lastMove[0].action == Action.ATTACK)
			return true;
		return false;
 	}

	this.isAttackingFrom = function(x, y)
	{
        if(this.isAttacking() &&
			this.lastMove[0].from[0] == x && this.lastMove[0].from[1] == y)
			return true;
		return false;
	}

	this.isAttackingTo = function(x, y)
	{
        if(this.isAttacking() &&
			this.lastMove[0].to[0] == x && this.lastMove[0].to[1] == y)
			return true;
		return false;
	}

	this.isCaptured = function(x, y)
	{
        if(this.lastMove && this.lastMove.length == 2 &&
			this.lastMove[1].action == Action.ATTACK &&
			this.lastMove[1].to[0] == x && this.lastMove[1].to[1] == y)
			return true;
		return false;
	}

    this.isCaptor = function(x, y)
    {
        if(this.lastMove && this.lastMove.length == 2 &&
            this.lastMove[1].action == Action.ATTACK &&
            this.lastMove[1].from[0] == x && this.lastMove[1].from[1] == y)
            return true;
        return false;
    }

	this.find_path = function(fromx, fromy, destx, desty, maxcost)
	{
		if(Math.abs(fromx-destx)+Math.abs(fromy-desty) > maxcost)
			return -1;

		var grid = new Array(width*height);
 		for(var i = 0; i < width * height; ++i) grid[i] = 0;

		var hierarkia = this;
		function dfs(x, y, cost)
		{
			var oldcost = grid[y * width + x];
			if(oldcost > 0 && oldcost <= cost) return -1;
			grid[y * width + x] = cost;

			if(x == destx && y == desty) return cost;
			if((x != fromx || y != fromy) && !hierarkia.empty(x, y)) return -1;

			var min = -1;
			if(cost < maxcost)
			{
 				var a = dfs((x < destx) ? (x+1) : (x-1), y, cost+1);
				if(a != -1) min = a;

 				var b = dfs(x, (y < desty) ? (y+1) : (y-1), cost+1); 
				if(min != -1 && b != -1) min = Math.min(min, b);
				else if(b != -1) min = b;

				var c = dfs((x < destx) ? (x-1) : (x+1), y, cost+1); 
				if(min != -1 && c != -1) min = Math.min(min, c);
				else if(c != -1) min = c;

				var d = dfs(x, (y < desty) ? (y-1) : (y+1), cost+1); 
				if(min != -1 && d != -1) min = Math.min(min, d);
				else if(d != -1) min = d;
			}

			return min;
		}

		return dfs(fromx, fromy, 0);
	}

	this.attackBlocked = function()
	{
        if(!this.lastMove
			|| this.lastMove.length != 2
			|| this.lastMove[0].action != Action.ATTACK) return false;

		var attacker = this.lastMove[0].from;
		var dest = this.lastMove[0].to;
		var firepower = this.firepower(attacker[0], attacker[1]);

		var cost = this.find_path(attacker[0], attacker[1], dest[0], dest[1], firepower);

		if(cost >= 0 && cost <= firepower)
			return false;

		return true;
	}
	
	this.canMove = function(x, y)
	{
		if(this.isAttacking() && !this.attackBlocked()) return this.isAttackingFrom(x, y);
        if(this.isCaptured(x, y)) return false;

		if(
	        (x > 0 && this.empty(x-1, y))  ||
	        (x < (width-2) && this.empty(x+1, y)) ||
	        (y > 0 && this.empty(x, y-1))  ||
	        (y < (height-2) && this.empty(x, y+1))
	        ) return true;
        return false;
    }
    
	this.canMoveTo = function(fromx, fromy, tox, toy) {
		if(this.isAttacking() && !this.attackBlocked()) return false;

	    function delta(from, to) { return (from == to) ? 0 : (from < to ? 1 : -1); }

	    if(!((fromx == tox) ^ (fromy == toy))) return false;
	    
	    if(this.empty(fromx, fromy)) return false;
		var piece = this.get(fromx, fromy);
		var movement =
			(piece.value == 1 && this.homezone(fromx, fromy) == piece.side) ?
			(piece.value+1) : piece.value;

	    if(movement < (Math.abs(tox - fromx) + Math.abs(toy - fromy))) return false;
	    
	    var dx = delta(fromx, tox), dy = delta(fromy, toy);		
		for(var x = fromx+dx, y = fromy+dy; x != tox+dx || y != toy+dy; x += dx, y += dy)
			if(!this.empty(x, y)) return false;   
	
	    return true;
    }

	this.canAttackTo = function(fromx, fromy, tox, toy)
	{
		if((this.isAttacking() && (this.attackBlocked() || !this.isAttackingFrom(fromx, fromy) || !this.isAttackingTo(tox, toy))))
			return false;

		if(this.empty(fromx, fromy) || this.empty(tox, toy)) return false;
 		if(this.get(fromx, fromy).side == this.get(tox, toy).side) return false;

		var fp = this.firepower(fromx, fromy);
		var path_len = this.find_path(fromx, fromy, tox, toy, fp);

		if(path_len <= 0 || path_len > fp) return false;
		
		return true;
	}
    	
	this.copy = function()
	{
        function copyArray(arr)
        {
            var out = new Array(arr.length);
            for(var i = 0; i < arr.length; ++i) out[i] = arr[i];
            return out;
        }
	
	    return new Hierarkia(info, copyArray(this.cells), this.lastMove);
	}
	
    function makeTurn(hierarkia, turn)
    {
        var h = hierarkia.copy();
		if(!hierarkia.lastMove) h.lastMove = [turn];
		else if(hierarkia.lastMove.length == 1) h.lastMove = [hierarkia.lastMove[0], turn];
		else h.lastMove = [hierarkia.lastMove[1], turn];
        
        if(turn.action == Action.MOVE)
        {
            var piece = h.cells[turn.from[0] + turn.from[1] * width];
            h.cells[turn.from[0] + turn.from[1] * width] = null;
            h.cells[turn.to[0] + turn.to[1] * width] = piece;
        } else if(turn.action == Action.ATTACK)
		{
			// Attack is a no-op, h.lastMove is used to determine the rules
		} else if(turn.action == Action.DESTROY)
		{
 			h.cells[turn.to[0] + turn.to[1] * width] = null;
		}

        return h;
    }

	this.makeMove = function(from, to)
	{
		return makeTurn(this, new Turn(Action.MOVE, from, to));
	}

	this.makeAttack = function(from, to)
	{
		if(!(this.lastMove && this.lastMove.length > 1)) throw "Cannot make attack turn in start of game";
		var action = (this.lastMove[0].action == Action.ATTACK) ?
			Action.DESTROY : Action.ATTACK;
		return makeTurn(this, new Turn(action, from, to));
	}

	this.pass = function()
	{
		return makeTurn(this, new Turn(Action.PASS, undefined, undefined));
	}
}

